class Solution(object):
    def maxValueOfCoins(self, piles, k):
        n = len(piles)
        DP = [0] * (k + 1)
        for st in piles:
            next_st = DP.copy()
            now = 0
            count = 0
            for num in st:
                now += num
                count += 1
                for i in range(0, k + 1 - count):
                    next_st[i + count] = max(next_st[i + count], DP[i] + now)
            DP = next_st
    
        return DP[-1]

                    

data = Solution()
piles = [[1,100,3],[7,8,9]]
k = 2
print(data.maxValueOfCoins(piles, k))